package developer.算法.栈.字符串解码;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * @author zhangyongkang
 * @time 2025/4/3 11:13
 * @description 给定一个经过编码的字符串，返回它解码后的字符串。
 * <p>
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 * <p>
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * <p>
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 * 示例 2：
 * <p>
 * 输入：s = "3[a2[c]]"
 * 输出："accaccacc"
 * 示例 3：
 * <p>
 * 输入：s = "2[abc]3[cd]ef"
 * 输出："abcabccdcdcdef"
 * 示例 4：
 * <p>
 * 输入：s = "abc3[cd]xyz"
 * 输出："abccdcdcdxyz"
 * <p>
 * 3[ab2[cd]]c2[b]c
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 30
 * s 由小写英文字母、数字和方括号 '[]' 组成
 * s 保证是一个 有效 的输入。
 * s 中所有整数的取值范围为 [1, 300]
 */
public class ZiFuChuanDeCode {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = solution.decodeString("23[a]56[b]89[c]");
        System.out.println(s);
    }

    static class Solution {

        List<Character> nums;

        public String decodeString(String s) {
            nums = new ArrayList<>();
            nums.add('0');
            nums.add('1');
            nums.add('2');
            nums.add('3');
            nums.add('4');
            nums.add('5');
            nums.add('6');
            nums.add('7');
            nums.add('8');
            nums.add('9');

            DoSomeThing doSomeThing = new DoSomeThing();
            doSomeThing.times = 1;
            doSomeThing.decode(s);
            return doSomeThing.getResult();
        }


        class DoSomeThing {
            int times;
            String currentStr = "";
            List<DoSomeThing> childrens = new ArrayList<>();

            public DoSomeThing decode(String s) {
                //判定当前是否为混合节点如果不是混合节点  那么直接进行赋值即可
                if (!s.contains("[")) {
                    currentStr = s;
                    return this;
                }
                //如果是混合节点 则一级一级进行分析
                boolean inTheStack = false;//是否处于栈中
                String currentStr = "";//当前的字符串
                String currentTimes = "";//当前的栈的次数
                Stack<Character> quoteStack = new Stack<>();
                DoSomeThing currentChildren = new DoSomeThing();

                for (int i = 0; i < s.length(); i++) {
                    char c = s.charAt(i);
                    if (nums.contains(c)) {//如果是数字 且不在栈中 那么就是后面栈的数量
                        if (inTheStack) {
                            currentStr += c;//如果在栈中 当作普通字符串处理
                        } else if (currentTimes.isEmpty()) {//说明准备开启一个新的栈 先对currentStr进行存储
                            currentChildren.times = 1;
                            childrens.add(currentChildren.decode(currentStr));
                            currentChildren = new DoSomeThing();

                            currentTimes = "";
                            currentStr = "";

                            currentTimes += c;//如果不在栈中 就是后面括号里面的数量
                        } else {
                            currentTimes += c;//如果不在栈中 就是后面括号里面的数量
                        }
                        continue;
                    }

                    if (c == '[') {//如果是左括号
                        if (inTheStack) {//如果处理栈中 当作普通字符串处理
                            currentStr += c;
                        } else {//说明处于一个新儿子的开头
                            inTheStack = true;
                        }
                        quoteStack.push(c);
                    } else if (c == ']') {//如果是右扩号
                        if (quoteStack.size() == 1) {//说明是最后一个  那么不添加当前数据到儿子
                            quoteStack.pop();
                            inTheStack = false;

                            currentChildren.times = Integer.parseInt(currentTimes.isEmpty() ? "1" : currentTimes);
                            childrens.add(currentChildren.decode(currentStr));

                            currentChildren = new DoSomeThing();//新儿子
                            currentStr = "";
                            currentTimes = "";
                        } else {//如果不是最后一个  那么肯定在栈中 出栈&
                            quoteStack.pop();
                            currentStr += c;
                        }
                    } else {
                        currentStr += c;
                        if (i == s.length() - 1) {//如果是最后一个且是普通字符 那么直接加入当前儿子
                            currentChildren.times = Integer.parseInt(currentTimes.isEmpty() ? "1" : currentTimes);
                            childrens.add(currentChildren.decode(currentStr));
                        }
                    }
                }
                return this;
            }

            public String getResult() {
                String str = "";
                if (childrens.isEmpty()) {
                    for (int i = 0; i < times; i++) {
                        str += currentStr;
                    }
                } else {
                    String children = childrens.stream().map(DoSomeThing::getResult)
                            .collect(Collectors.joining(""));
                    for (int i = 0; i < times; i++) {
                        str += children;
                    }
                }
                return str;
            }
        }
    }

    class SolutionOfficial {
        String src;
        int ptr;

        public String decodeString(String s) {
            src = s;
            ptr = 0;
            return getString();
        }

        public String getString() {
            if (ptr == src.length() || src.charAt(ptr) == ']') {
                // String -> EPS
                return "";
            }

            char cur = src.charAt(ptr);
            int repTime = 1;
            String ret = "";

            if (Character.isDigit(cur)) {
                // String -> Digits [ String ] String
                // 解析 Digits
                repTime = getDigits();
                // 过滤左括号
                ++ptr;
                // 解析 String
                String str = getString();
                // 过滤右括号
                ++ptr;
                // 构造字符串
                while (repTime-- > 0) {
                    ret += str;
                }
            } else if (Character.isLetter(cur)) {
                // String -> Char String
                // 解析 Char
                ret = String.valueOf(src.charAt(ptr++));
            }

            return ret + getString();
        }

        public int getDigits() {
            int ret = 0;
            while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
                ret = ret * 10 + src.charAt(ptr++) - '0';
            }
            return ret;
        }
    }

}
